package LearnAlgorithm.c_递归and查找排序;

/*
给定一个无序数组arr ,求出需要排序的最短子数组长度
要求:
- 0(N)
如输入: arr={2,3,7,5,4,6} ,返回4 ,因为只有{7,5,4,6}需要排序
 */
public class q乱序数组求最小需要排序的子数组 {
	public static void main(String[] args) {
		int[] arr = new int[] {2,3,7,5,4,6};
//		int[] findSegment = findSegment(arr, arr.length);
//		System.out.print("[" + findSegment[0] + "," + findSegment[1] + "]");	
		int findSegmentReturnInt = findSegmentReturnInt(arr, arr.length);
		System.out.println(findSegmentReturnInt);
	}
	
	public static int findSegmentReturnInt(int[] arr, int length) {
		int left = -1;
		int right = -1;
		int max = arr[0];
		int min = arr[length - 1];
		for (int i = 0; i < length; i++) { 
			if (arr[i] > max) { 
				max = arr[i];
			} else if (arr[i] < max) { 
				right = i;
			}
		}
		for (int i = length - 1; i >= 0; i--) { 
			if (arr[i] < min) { 
				min = arr[i];
			} else if (arr[i] > min) { 
				left = i;
			}
		}
		if (left == -1 || right == -1) { 
			return 0;
		}
		return right - left + 1;//返回需要排序的元素“个数”
	}	
	
	/**
	 * 这个方法只考虑到了升序这个顺序
	 * 如果“有序”意味着升序降序都可以，那么需要改进算法
	 * @param arr
	 * @param n
	 * @return
	 */
	public static int[] findSegment(int[] arr, int n) {
		int left = -1;
		int right = -1;
		int max = arr[0];
		int min = arr[n - 1];
		//拓展右端点:更新历史最高，只有右侧出现比历史最高低的，就应该将右边界扩展到此处
		for (int i = 0; i < n; i++) {//不用担心意外，担心没考虑到什么元素的情况
			if (arr[i] > max) {//这里的步骤看不懂，就画个图形，就自然发现全考虑到了
				max = arr[i];
			} else if (arr[i] < max) {//只要低于历史高峰，就要扩展需排序区间的右端点；等于的情况不算
				right = i;
			}
		}
		//找左端点:更新历史最低，只要左侧出现比历史最低高的，就应该将左边界扩展到此处
		for (int i = n - 1; i >= 0; i--) {//不用担心意外，担心没考虑到什么元素的情况
			if (arr[i] < min) {//这里的步骤看不懂，就画个图形，就自然发现全考虑到了
				min = arr[i];
			} else if (arr[i] > min) {//只要高于历史低谷，就要扩展需排序区间的左端点；等于的情况不算
				left = i;
			}
		}
		if (left == -1 || right == -1) {//如果发现某一端没有更新过，那就代表这个数组本来就是升序有序
			return new int[] {0,0};
		}
		return new int[] {left, right};
	}
}
